//反转链表



/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode reverseList(ListNode head) {
//        ListNode cur = new ListNode;
//        ListNode kk = new ListNode;
//        ListNode cc = new ListNode;
//        cur = head.next;
//        head.next = null;
//        kk = cur;
//        cc = kk.next;
//        while(cc != null){
//            ListNode.addFirst(kk.val);
//            head = kk;
//            kk = cc;
//            cc = cc.next;
//        }
//        return head;
//    }
//}
//
//class Solution {
//    public ListNode reverseList(ListNode head) {
//        if(head == null){
//            return null;
//        }
//        if(head.next == null){
//            return head;
//        }
//        ListNode kk = head.next;
//        head.next = null;
//        while(kk != null){
//            ListNode cc = kk.next;
//            kk.next = head;
//            head = kk;
//            kk = cc;
//        }
//        return head;
//
//    }
//}
//class Solution {
//    public ListNode reverseList(ListNode head) {
//        if(head == null){
//            return null;
//        }
//        if(head.next == null){
//            return head;
//        }
//        ListNode kk = head.next;
//        ListNode cc = kk.next;
//        head.next = null;
//        while(kk != null){
//            kk.next = head;
//            head = kk;
//            kk = cc;
//            cc = kk.next;
//        }
//        return head;
//
//    }
//}

//链表的中间节点
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode middleNode(ListNode head) {
//        ListNode slow= head;
//        ListNode quick= head;
//        while (quick != null && quick.next != null){
//            slow = slow.next;
//            quick = quick.next.next;
//        }
//        return slow;
//
//    }
//}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */


//返回倒数第 k 个节点
//class Solution {
//    public int kthToLast(ListNode head, int k) {
//        ListNode quick = head;
//        ListNode slow = head;
//        for(int i=0; i<k-1; i++){
//            quick = quick.next;
//        }
//        while(quick.next != null){
//            quick = quick.next;
//            slow = slow.next;
//        }
//        return slow.val;
//    }
//}

//合并两个有序链表11111111111111111111
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        ListNode handA = list1;
//        ListNode handB = list2;
//        ListNode mov = new ListNode();
//        ListNode eco = new ListNode();
//        if(list1 == null && list2 == null){
//            return null;
//        }
//        if(list1 == null){
//            return list2;
//        }
//        if(list2 == null){
//            return list1;
//        }
//        if(handA.val>handB.val){
//            eco.next = handB;
//            handB = handB.next;
//            mov = eco.next;
//        }else{
//            eco.next = handA;
//            handA = handA.next;
//            mov = eco.next;
//        }
//        while(handA != null && handB != null){
//            if(handA.val > handB.val){
//                mov.next = handB;
//                handB = handB.next;
//                mov = mov.next;
//            }else{
//                mov.next = handA;
//                mov = mov.next;
//                handA = handA.next;
//
//            }
//        }
//        while(handA != null){
//            mov.next = handA;
//            handA = handA.next;
//            mov = mov.next;
//        }
//        while(handB != null){
//            mov.next = handB;
//            handB = handB.next;
//            mov = mov.next;
//        }
//        return eco.next;
//    }
//
//}

//回文链表
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public boolean isPalindrome(ListNode head) {
//        if(head == null){
//            return false;
//        }
//        if(head.next == null){
//            return true;
//        }
//        ListNode slow = head;
//        ListNode fast = head;
//        while(fast != null && fast.next!= null){
//            slow = slow.next;
//            fast = fast.next.next;
//        }
//        ListNode kk = slow.next;
//        while(kk != null){
//            ListNode cc = kk.next;
//            kk.next = slow;
//            slow = kk;
//            kk = cc;
//        }
//        while(head != slow){
//            if(head.val != slow.val){
//                return false;
//            }
//            if(head.next == slow){
//                return true;
//            }
//            head = head.next;
//            slow = slow.next;
//        }
//        return true;
//    }
//}

//
//for (ListNode p = headA; p != null; p = p.next) {
//        for (ListNode q = headB; q != null; q = q.next) {
//        if (p == q)
//        return p;
//        }
//        }
//        return null;
//
//
//
//
//        while(headA != null){
//        while(headB != null){
//        if(headA == headB){
//        return headA;
//        }
//        headB = headB.next;
//        }
//        headA = headA.next;
//        }
//        return null;

//环形链表

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
//public class Solution {
//    public boolean hasCycle(ListNode head) {
//        if(head == null){
//            return false;
//        }
//        ListNode fast = head.next;
//        ListNode slow = head;
//        while(fast != null && fast.next != null){
//            if(fast == slow){
//                return true;
//            }
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//        return false;
//    }
//}


//
//public class MySingleList {
//    static class ListNode {
//        public int val;//节点的值域
//        public ListNode next;//下一个节点的地址
//
//        public ListNode(int val) {
//            this.val = val;
//        }
//
//    }
//
//
//    public ListNode head;//表示当前链表的头节点
//
//    public void createList() {
//
//        ListNode node1 = new ListNode(12);
//        ListNode node2 = new ListNode(23);
//        ListNode node3 = new ListNode(34);
//        ListNode node4 = new ListNode(45);
//        ListNode node5 = new ListNode(56);
//
//        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
//        node4.next = node5;
//
//        this.head = node1;
//
//    }
//
//    //头插法
//    public void addFirst(int data) {
//        ListNode node = new ListNode(data);
//        node.next = head;
//        head = node;
//    }
//    //尾插法
//    public void addLast(int data) {
//        ListNode node = new ListNode(data);
//        ListNode cur = head;
//        if (head == null) {
//            head = node;
//            return;
//        }
//        while(cur.next != null) {
//            cur = cur.next;
//        }
//        cur.next = node;
//    }
//    //任意位置插入,第一个数据节点为0号下标
//    public void addIndex(int index,int data) {
//        ListNode node = new ListNode(data);
//        ListNode cur = head;
//        if (index < 0 || index >size()) {
//            System.out.println("位置不合法");
//        }
//        else if (index == 0) {
//            addFirst(data);
//        }else if (index == size()) {
//            addLast(data);
//        }else {
//            for (int i = 0; i < index-1; i++) {
//                cur = cur.next;
//            }
//            node.next = cur.next;
//            cur.next = node;
//        }
//    }
//    //查找是否包含关键字key是否在单链表当中
//    public boolean contains(int key){
//        ListNode cur = head;
//        while (cur != null){
//            if (cur.val == key){
//                return true;
//            }
//            cur = cur.next;
//        }
//        return false;
//    }
//    //删除第一次出现关键字为key的节点
//    public void remove(int key){
//        ListNode cur = head;
//        if (head.val == key){
//            head = head.next;
//            return;
//        }
//        while(cur.next != null){
//            if (cur.next.val == key){
//                cur.next = cur.next.next;
//                return;
//            }
//            cur = cur.next;
//        }
//        System.out.println("没有这个数字");
//    }
//    //删除所有值为key的节点
//    public void removeAllKey(int key){
//        if (head == null){
//        }
//        while (head.val == key){
//            head = head.next;
//        }
//        ListNode cur = head.next;
//        ListNode prev = head;
//        while(cur != null){
//            if (cur.val == key){
//                cur = cur.next;
//                prev.next = cur;
//            }else {
//                cur = cur.next;
//                prev = prev.next;
//            }
//        }
//    }
//    //得到单链表的长度
//    public int size(){
//        ListNode cur = head;
//        int sum = 0;
//        while(cur != null){
//            sum++;
//            cur = cur.next;
//        }
//        return sum;
//    }
//    public void display() {
//        ListNode cur = head;
//        while (cur != null) {
//            System.out.print(cur.val+" ");
//            cur = cur.next;
//        }
//        System.out.println();
//    }
//    public void clear(){
//        head = null;
//    }
//
//    public static void main(String[] args) {
//        MySingleList mySingleList = new MySingleList();
//        mySingleList.createList();
//        mySingleList.addFirst(3);
//        mySingleList.addFirst(2);
//        mySingleList.addFirst(1);
//        mySingleList.display();
//        mySingleList.addLast(7);
//        mySingleList.addLast(8);
//        mySingleList.addLast(9);
//        mySingleList.addLast(9);
//        mySingleList.display();
//        mySingleList.addIndex(3, 4);
//        mySingleList.display();
//        System.out.println(mySingleList.contains(23));
//        System.out.println(mySingleList.contains(99));
//        mySingleList.remove(9);
//        mySingleList.display();
//        mySingleList.addFirst(1);
//        mySingleList.addFirst(1);
//        mySingleList.display();
//        mySingleList.removeAllKey(1);
//        mySingleList.display();
//        mySingleList.addFirst(2);
//        mySingleList.addFirst(2);
//        mySingleList.addFirst(2);
//        mySingleList.addFirst(2);
//        mySingleList.addFirst(1);
//        mySingleList.addFirst(1);
//        mySingleList.removeAllKey(2);
//        mySingleList.display();
//        mySingleList.clear();
//        mySingleList.display();
//        mySingleList.removeAllKey(3);
//        mySingleList.display();
//          mySingleList.addLast(1);
//        mySingleList.addLast(1);
//        mySingleList.addLast(1);
//        mySingleList.addLast(1);
//        mySingleList.addLast(1);
//        mySingleList.addLast(2);
//        MySingleList kk = deleteDuplication(mySingleList.head);
//        kk.display();
//    }
//}

///**
// * @Author 12629
// * @Description：
// */
//public class MyLinkedList {
//    static class ListNode {
//        private int val;
//        private ListNode prev;//前驱
//        private ListNode next;//后继
//
//        public ListNode(int val) {
//            this.val = val;
//        }
//    }
//
//    public ListNode head;//双向链表的头节点
//    public ListNode last;//双向链表的尾巴
//
//    //得到链表的长度
//    public int size(){
//        ListNode cur = head;
//        int num = 0;
//        while (cur != null){
//            cur = cur.next;
//            num++;
//        }
//        return num;
//    }
//    public void display(){
//        ListNode cur = head;
//        while(cur != null){
//            System.out.print(cur.val+" ");
//            cur = cur.next;
//        }
//        System.out.println();
//    }
//
//    //查找是否包含关键字key是否在链表当中
//    public boolean contains(int key){
//        ListNode cur = head;
//        while (cur != null){
//            if (cur.val == key){
//                return true;
//            }
//            cur = cur.next;
//        }
//        return false;
//    }
//    //头插法
//    public void addFirst(int data){
//        ListNode cur = new ListNode(data);
//        if (head == null){
//            head = cur;
//            last = cur;
//        }else {
//            cur.next = head;
//            head.prev = cur;
//            head = cur;
//        }
//    }
//
//    //尾插法
//    public void addLast(int data){
//        ListNode cur = new ListNode(data);
//        if (head == null){
//            head = cur;
//            last = cur;
//        }else {
//            last.next = cur;
//            cur.prev = last;
//            last = cur;
//        }
//    }
//
//    //任意位置插入,第一个数据节点为0号下标
//    public void addIndex(int index,int data) {
//        if (index == 0) {
//            addFirst(index);
//        } else if (index == size()) {
//            addLast(data);
//        } else {
//            ListNode node = new ListNode(data);
//            ListNode sea = searchIndex(index);
//            node.next = sea;
//            node.prev = sea.prev;
//            sea.prev = node;
//            node.prev.next = node;
//        }
//    }
//
//    private ListNode searchIndex(int index) {
//        ListNode cur = head;
//        if (index < 0 || index >= size()){
//            System.out.println("位置不合法");
//            return null;
//        }
//        for (int i = 0; i < index; i++) {
//            cur = cur.next;
//        }
//        return cur;
//    }
//
//    private void checkIndex(int index) {
//
//    }
//
//
//    //删除第一次出现关键字为key的节点
//    public void remove(int key){
//        ListNode node = head;
//        while (node != null){
//            if (head.val == key){
//                head = head.next;
//                if (head != null) {
//                    head.prev = null;
//                }else {
//                    last = null;
//                }
//                return;
//            }else if (node.next == null && last.val == key){
//                last = last.prev;
//                last.next = null;
//                return;
//            }else if (node.val == key){
//                node.prev.next = node.next;
//                node.next.prev = node.prev;
//                return;
//            }
//            node = node.next;
//        }
//        System.out.println("没有这个");
//    }
//    //删除所有值为key的节点
//    public void removeAllKey(int key){
//        ListNode node = head;
//        while (node != null){
//            if (head.val == key){
//                head = head.next;
//                if (head != null) {
//                    head.prev = null;
//                }else {
//                    last = null;
//                }
//            }else if (node.next == null && last.val == key){
//                last = last.prev;
//                last.next = null;
//            }else if (node.val == key){
//                node.prev.next = node.next;
//                node.next.prev = node.prev;
//            }
//            node = node.next;
//        }
//    }
//
//    public void clear(){
//        head = null;
//        last = null;
//    }
//
//    public static void main(String[] args) {
//        MyLinkedList myLinkedList = new MyLinkedList();
//        myLinkedList.addFirst(1);
//        myLinkedList.display();
//        myLinkedList.addLast(3);
//        myLinkedList.display();
//        System.out.println(myLinkedList.size());
//        System.out.println(myLinkedList.contains(2));
//        System.out.println(myLinkedList.contains(99));
//        myLinkedList.addIndex(1, 2);
//        myLinkedList.display();
//        myLinkedList.remove(2);
//        myLinkedList.display();
//        myLinkedList.addLast(4);
//        myLinkedList.addLast(5);
//        myLinkedList.addLast(6);
//        myLinkedList.addLast(6);
//        myLinkedList.addLast(7);
//        myLinkedList.display();
//        myLinkedList.remove(1);
//        myLinkedList.display();
//        myLinkedList.removeAllKey(6);
//        myLinkedList.display();
//        myLinkedList.clear();
//        myLinkedList.addFirst(1);
//        myLinkedList.addFirst(1);
//        myLinkedList.addFirst(1);
//        myLinkedList.addFirst(1);
//        myLinkedList.addFirst(1);
//        myLinkedList.addFirst(1);
//        myLinkedList.addFirst(1);
//        myLinkedList.addFirst(1);
//        myLinkedList.addFirst(1);
//        myLinkedList.addFirst(2);
//        myLinkedList.display();
//        myLinkedList.remove(1);
//        myLinkedList.display();
//        myLinkedList.addLast(2);
//        myLinkedList.display();
//        myLinkedList.remove(2);
//        myLinkedList.display();
//        myLinkedList.addFirst(2);
//        myLinkedList.display();
//        myLinkedList.remove(2);
//        myLinkedList.display();
//        myLinkedList.addFirst(3);
//        myLinkedList.addFirst(2);
//        myLinkedList.addLast(3);
//        myLinkedList.display();
//        myLinkedList.remove(3);
//        myLinkedList.display();
//        myLinkedList.removeAllKey(1);
//        myLinkedList.display();
//        myLinkedList.clear();
//        myLinkedList.display();
//        System.out.println(1);
//
//    }
//}
public class MyLinkedList {
//    public static void main(String[] args) {
//        //构造一个空的LinkedList
//        List<Integer>list1 = new LinkedList<>();
//
//        List<String>list2 = new java.util.ArrayList<>();
//        list2.add("haha");
//        list2.add("hehe");
//        //使用ArrayList构造LinkedList
//        List<String>list3 = new LinkedList<>(list2);

    public static void main(String[] args) {
        Stack<Integer>s = new Stack<>();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println(s.size());//获取栈中有效元素个数
        System.out.println(s.peek());//获取栈顶元素
        s.pop();//4出栈，栈中剩余1 2 3，栈顶元素为3
        System.out.println(s.pop());//3出栈，栈中剩余1 2，栈顶元素为2
        if (s.empty()){
            System.out.println("栈空");
        }else {
            System.out.println(s.size());
        }
    }
}

